#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 200005;
int st[maxn][30],n,m;

void init(){
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)<=n+1;i++){
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}

int rmq(int l,int r){
	int k=0;
	while((1<<k)<=(r-l+1))k++;
	k--;
	return max(st[l][k],st[r-(1<<k)+1][k]);
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>st[i][0];
	}
	cin>>m;
	init();
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		cout<<rmq(a,b)<<endl;
	}
	
}